package offer;

import java.util.ArrayList;

//字符串的排列
public class T28 {

    public ArrayList<String> Permutation(String str) {
        ArrayList<String> list = new ArrayList<String>();
        if (str.length()<=0) return list;
        char ch[] = str.toCharArray();
        for (int i = 0; i < ch.length; i++) {
            for (int j = 0; j < ch.length-i-1; j++) {
                 if (ch[j]>ch[j+1]) {
                     char temp = ch[j];
                     ch[j] = ch[j+1];
                     ch[j+1] = temp;
                 }
            }
        }

        list.add(new String(ch));
        if (ch.length<=1) return list;
        while (true) {

            int leftIndex = ch.length-1;
            while (leftIndex>=1&&ch[leftIndex-1]>=ch[leftIndex]) {
                leftIndex--;
            }
            if (leftIndex==0) break;
            int rightIndex = leftIndex;
            while (rightIndex<ch.length&&ch[rightIndex]>ch[leftIndex-1]) rightIndex++;
            char temp = ch[leftIndex-1];
            ch[leftIndex-1] = ch[rightIndex-1];
            ch[rightIndex-1] = temp;
            //反转
            for (int i = 0; i <(ch.length-leftIndex)/2 ; i++) {
                temp = ch[leftIndex+i];
                ch[leftIndex+i] = ch[ch.length-1-i];
                ch[ch.length-1-i] = temp;
                System.out.println(i);
            }
            list.add(new String(ch));
        }

        return list;
    }
    public static void main ( String[] args) {
        System.out.println(new T28().Permutation("accca"));

    }
}
